package com.itheima.suanfa;

/*
二分查找
思路

需要两个索引 左边 0和 右边 最大索引
获取中间索引= (左边+右边)/2
判断被查找的数与索引上的数
是什么关系
相等  找到了 结束
要找的数比 索引上的数小了  在左边   右边= 中间-1
要找的数 比 索引上的数 大  在右边   左边= 中间+1
死循环 找
直到 左边>右边

 */
public class Demo01 {


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int i = 15;
        System.out.println(binarySearch(arr, i));

    }

    //定义方法 完成  二分查找
    //参数  两个  数组  需要查找的数
    // 返回值类型  int
    public static int binarySearch(int[] arr, int number) {
        //需要两个索引 左边 0和 右边 最大索引
        int left = 0;
        int right = arr.length - 1;
        //获取中间索引= (左边+右边)/2
        while (left<=right) {
            int mid = (left + right) >> 1;
            //判断被查找的数与索引上的数
            if (number == arr[mid]) {
                //是什么关系
                //相等  找到了 结束
                return mid;
            } else if (number < arr[mid]) {
                //要找的数比 索引上的数小了  在左边   右边= 中间-1
                right = mid - 1;
            } else {
                //要找的数 比 索引上的数 大  在右边   左边= 中间+1
                left = mid + 1;
            }
            //死循环 找
            //直到 左边>右边
            /*if (left > right) {
                break;
            }*/
        }

        return -(left+1);


    }

}
